Graph, Tree and its types - DSA Cheatsheet

Graph: A collection of nodes (also called vertices) and edges connecting pairs of nodes, used to represent relationships or connections in a network.

Edge (E ): A connection or link between two nodes in a graph.

Node or Vertex (V ): An individual element or point in a graph that can be connected to other nodes via edg

Subgraph: A subset of a graph's nodes and edges that forms a graph on its own.

Degree: The degree of a vertex in a graph is the number of edges connected to it.

Path: A path in a graph is a sequence of vertices connected by edges, where each edge is traversed once. A simple path does not repeat any vertices or edges.

Cycles: A graph with at least one cycle or a path that starts and ends at the same vertex without repeating any edges or vertices.

Types of Graph:

*Definition*	*Image Representation*
Undirected Graphs: A graph in which edges have no direction. Example: A social network graph where friendships are not directional.
Directed Graphs (Digraphs): A graph in which edges have a direction. Example: A web page graph where links between pages are directional.
Weighted Graphs: A graph in which edges have weights or costs associated with them. Example: A road network graph where the weights can represent the distance between two cities.
Unweighted Graphs: A graph in which edges have no weights or costs associated with them. Example: A social network graph where the edges represent friendships.
Complete Graphs: A graph in which each vertex is connected to every other vertex. Example: A tournament graph where every player plays against every other player.
Bipartite Graphs: A graph in which the vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Example: A job applicant graph where the vertices can be divided into job applicants and job openings.
Connected Graph: A graph where there is a path between every pair of vertices. Example: A fully reachable computer network.
Disconnected Graph: A graph with at least one pair of vertices that are not connected by a path.
Trees (Simple Graph): In a connected graph, there is always a path between any two nodes. It does not contain any cycles, which means there is no path that starts and ends at the same vertex without repeating any edges or vertices.
Sparse Graphs: A graph with relatively few edges compared to the number of vertices. Example: A chemical reaction graph where each vertex represents a chemical compound and each edge represents a reaction between two compounds.
Dense Graphs: A graph with many edges compared to the number of vertices. Example: A social network graph where each vertex represents a person and each edge represents a friendship.
Finite Graphs: A graph with a finite number of vertices and edges.
Infinite Graphs: A graph with an infinite number of vertices or edges.
Trivial Graph: A graph with a single vertex and no edges.
Pseudo Graph: A graph that allows loops and multiple edges. Example: A network with self-connections and multiple connections.
Multi Graph: A graph with multiple edges between two vertices but no self loop. Example: A transportation network with multiple routes between cities.
Null Graph: A graph with no edges. Example: A set of isolated nodes.
Regular Graph: A graph where each vertex has the same number of edges.
Labeled Graph: A graph where vertices or edges have labels. Example: A graph where nodes are labeled with names and edges with relationships.
Cyclic Graph: A graph that contains at least one cycle.
Acyclic Graph: A graph with no cycles. Example: A hierarchy or tree structure.

Applications of Graph

Networks- Social Networks, Transportation Network, Communcation Network.
Computer Science- Data Structure and Algorithm.
Biology- Genomics, Ecology
Business and Finance- Supply Chain Managemetn, Stock Market Analysis.
Geography- Geographical Information Systems(GIS).
Recommendation Systems- E-commerse, Search Engine

Advantages of Graph

Versatility: Graphs can model a wide variety of relationships and structures, making them applicable in diverse domains.
Flexibility: Graphs can easily represent complex and dynamic systems.
Visualization: Graphs provide intuitive visual representations that aid in understanding and analysis.
Efficiency: Many graph algorithms have efficient implementations, enabling the solution of complex problems.
Modularity: Graphs allow the decomposition of systems into smaller, manageable components.

Disadvantages of Graph

Complexity: Some graph problems are NP-hard, making them computationally expensive to solve.
Data Representation: Representing large graphs in memory can be memory-intensive.
Ambiguity: Interpreting large or densely connected graphs can be challenging.
Scalability: Analyzing and processing large-scale graphs may require specialized infrastructure and algorithms.
Data Quality: Graph analysis heavily relies on the quality and completeness of input data, which may not always be available or reliable.

Tree and its properties

A Tree is a non-linear data structure and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

Some important properties of tree data structure:

Root: The topmost node in a tree, with no parent.
Key: The value stored in a node.
Edge: A connection between two nodes.
Parent: A node that has one or more children.
Subtree: A tree consisting of a node and all its descendants.
Child: A node directly connected to another node when moving away from the root.
Siblings: Nodes that share the same parent.
Leaf Nodes (Leaves): Nodes with no children.
Height of Tree: The length of the longest path from the root to a leaf.
Levels: The level of a node is the number of edges from the root to that node. The root is at level 0.

Types of Tree based on no. of childs.

Type name and definition	Image representation
Binary Tree - A binary Tree is defined as a Tree data structure with at most 2 children. we typically name them the left and right child.
Ternary Tree - A Ternary Tree is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”.
N-ary Tree (Generic Tree) - Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed).

Some more important tree types:

Binary Search Tree - It is a node-based binary tree data structure that has the following properties:
→ The left subtree of a node contains only nodes with keys lesser than the node’s key.
→ The right subtree of a node contains only nodes with keys greater than the node’s key.
→ The left and right subtree each must also be a binary search tree.

AVL Tree - It is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Red Black Tree - It is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black). These colors are used to ensure that the tree remains balanced during insertions and deletions.

B-tree - A B-tree is a self-balancing tree data structure designed for handling large datasets efficiently. It maintains sorted data, with each node capable of holding multiple keys and children. By ensuring that all leaf nodes are at the same level and minimizing disk accesses, B-trees provide fast search, insertion, and deletion operations, making them ideal for use in databases and file systems.

B+ tree - In a B+ tree, all data is stored in the leaf nodes, while internal nodes are used solely for indexing and routing purposes. This design ensures that all leaf nodes are at the same level, simplifying traversal and range queries.

Suggetested Articles